/*
 * @lc app=leetcode id=493 lang=cpp
 *
 * [493] Reverse Pairs
 */

// @lc code=start
class Solution {
public:
int reversePairs(vector<int>& nums) {
        vector<int> temp(nums.size(), 0);
        return  mergeSort(nums, temp, 0, nums.size() - 1);;
    }
    int mergeSort(vector<int>& nums, vector<int>& temp, int left, int right) {
        if(left >= right) return 0;
        int mid = left + ((right - left) >> 1);
        int count = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid+1, right);
        int i = left, j = mid+1, k = left;
        while(i <= mid && j <= right) {
            if((long)nums[i] > 2 * (long)nums[j]) {
                count += (mid -i + 1);
                ++j;
            }
            else
                ++i;
        }
        i = left; 
        j = mid+1;
        while(i <= mid &&  j <= right) {
            if(nums[i] > nums[j])
                temp[k++] = nums[j++];
            else
                temp[k++] = nums[i++];
        }
        while(i <= mid) temp[k++] = nums[i++];
        while(j <= right) temp[k++] = nums[j++];
        copy(temp.begin()+left, temp.begin()+right+1, nums.begin()+left);
        return count;
    }
};
// @lc code=end

